package Algorithm.jianzhi;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/*
数组中重复的数字
找出数组中重复的数字。


在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Jian03 {
//方案一：暴力求解
//时间复杂度是 O(n^2)
//空间复杂度是 O(1)

public int main1(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            if (nums[i]==nums[j]){
                return nums[i];
            }
        }
    }
    return -1;
}

//方案二：哈希查找
//时间复杂度是 O(n)
//    空间复杂度是 O(n)
public int main2(int[] nums){
    //初始化一个哈希表
    Set<Integer> set=new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        //判断当前元素是否存在
        if (set.contains(nums[i])) {
            return nums[i];
        }
        //否则，存入哈希表，以后查找
        set.add(nums[i]);

    }
    return -1;
}
//数组代替哈希表
//时间复杂度是 O(n)
//    空间复杂度是 O(n)
public int main3(int[] nums) {
    //初始化一个数组
    int[] bucket = new int[nums.length];
    Arrays.fill(bucket,-1);

    for (int i = 0; i < nums.length; i++) {
        //判断当前元素是否已经存在
        if (bucket[nums[i]]!=-1) {
            //如果存在，则直接返回
            return nums[i];
        }
        //否则，将当前元素作为索引，当前元素下标作为值，填入数组，方便后续查找判重
        bucket[nums[i]]=i;
    }
    return -1;
}
//最优解法
public int main4(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (i != nums[i]) {
            if (nums[i]==nums[nums[i]]) {
                return nums[i];
            }
            //否则，交换
            int tmp=nums[nums[i]];
            nums[nums[i]]=nums[i];
            tmp=nums[i];
        }
        
    }
return -1;
}


}
